1. Field of the Invention
The present invention relates to video processing. More specifically, the present invention relates to a method and apparatus for performing a rotating sample of locations in an image, which is especially useful for a computationally inexpensive transmission of a sequence of images from a transmitter to a receiver using a temporal redundancy compression technique.
2. Background Information
The proliferation of computer systems which provide higher quality imagery at lower cost has resulted in a demand for applications such as video conferencing. Due to the large amount of data which must be transmitted in such applications at real time or near real time rates, there has increased a need for a means for reducing the amount of data transmitted between computer systems due to the upper limits of communication media between computer systems. Many prior art solutions to such data reduction, also known as compression, rely upon computationally-expensive means. An overview of some of these techniques will now be discussed.
In general, video conferencing involves the transmission and reception of video images and audio information. In a typical application, multiple users of a video conferencing system view the conference on a display screen and are themselves viewed by camera typically attached to the display. Conferences can be carded out over a number of communication media, including ISDN connections or local area networks (LANs), referred to as "links." As previously discussed, because of the low bandwidth of such links in relation to typical full screen resolution and full frame rate of moving imagery (e.g., 30 frames per second at 640.times.480 pixel resolution), some sort of compression needs to be performed on the data in order to allow transmission.
One prior approach to compression is generally referred to as selective update. Selective update is a technique wherein portions of an image are transferred between a transmitter and a receiver that have changed from a previous time period (e.g., a previous frame). This results in reducing the amount of data being transmitted. These types of algorithms generally reduce the amount of temporal redundancy. These techniques take advantage of the similarities between images or among sequence of images. Yet another approach to the compression of images are those which exploit spatial redundancy. These algorithms typically transform an image into a format which can be more compactly described for transmission. On reception of such an image the receiver (or decompressor) reverses the transformation required for display. For example, the video teleconferencing standard P*64 uses a combination of temporal and spatial compression techniques to compress a video bit stream.
A variety of techniques for reducing the data in video bit streams based on temporal redundancy, spatial redundancy, or a combination of both, are present in the prior art. For example, the CCIR 601 4:2:2 standard uses a spatial redundancy technique to compress a single video frame. The CCIR 601 standard exploits the fact that the human eye is less sensitive to changes in chrominance than to changes in luminance. CCIR 601 pixels change luminance every pixel but change chrominance only every other pixel. The human eye is also insensitive to higher frequencies, tending to average rapidly changing pixel values. Dithering algorithms exploit the human eye's averaging ability. Dithering trades spatial resolution for color or intensity resolution, representing an image such that over a given area its average intensity or color is correct. More sophisticated approaches to compression filter high frequencies of image data removing data and/or image information unnoticed by the human eye. Such schemes typically filter high frequencies by first dividing the image into tiles such as 4.times.4 or 8.times.8 pixels, and filtering the tiles individually.
Temporal redundancy technique exploit the redundancy and sequences of images over time. These schemes take advantage of the fact that in many video applications such as video conferencing there are typically large portions of the transmitted image which do not change significantly from frame-to-frame. More elaborate schemes attempt to estimate the motion in a moving picture such as when a camera pans from left to right. These techniques are known generally as motion estimation algorithms. Motion estimation relies upon translating and copying portions of an earlier frame and only selectively updating those pixels which have changed to construct a frame.
Yet other techniques for removing both temporal and spatial redundancy use even more sophisticated techniques such as vector quantization, wherein similar data either spatially or temporally, is arranged into a code book and similar portions of the image are transmitted based upon code book indices. Again, techniques such as those discussed above, or those utilizing vector quantization tend to be computationally expensive. These prior art processes present a substantial load on the devices, and pose a substantial upper limit on the performance of such techniques. In a multi-tasking environment (e.g. a computer workstation), the processor cannot be completely consumed by such an application due to the need to perform other tasks. Therefore, what is desired is a low cost compression scheme that alleviates some of this load, but yet, provides acceptable image quality for applications such as video teleconferencing.